package com.njupt.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/22 10:12
 * @Description: 完美二叉树 116填充每个节点的下一个右侧节点指针
 * @Version: 1.0
 */


public class Connect {

    public PerfectNode connect(PerfectNode root) {
        Deque<PerfectNode> queue = new LinkedList<>();
        if(root == null) return root;

        queue.addLast(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            PerfectNode node = null;
            for (int i = 0; i < size; i++) {
                node = queue.pop();
                if(i != size-1){
                    node.next = queue.peekFirst();
                }


                if(node.left != null) queue.addLast(node.left);
                if(node.right != null) queue.addLast(node.right);
            }
            node.next = null;
        }
        return root;
    }


    public static void main(String[] args) {
        PerfectNode root = new PerfectNode(1);
        root.left = new PerfectNode(2);
        root.right = new PerfectNode(3);
        root.left.left = new PerfectNode(4);
        root.left.right = new PerfectNode(5);
        root.right.left = new PerfectNode(6);
        root.right.right = new PerfectNode(7);

        Connect test = new Connect();
        PerfectNode perfectNode = test.connect(root);
        System.out.println(perfectNode);
//        Deque<PerfectNode> queue = new LinkedList<>();
//        queue.addLast(perfectNode);
//        while(!queue.isEmpty()){
//            int size = queue.size();
//            for (int i = 0; i < size; i++) {
//                PerfectNode node = queue.pollFirst();
//                System.out.println("当前节点：" + node.val);
//            }
//        }

    }
}
